Network probing for capacity is commonly performed using one of many available methods, the ones most relevant to this invention being the Variable Probing Size (VPS) method and the Probe Gap Model (PGM) method.
VPS probing measures round-trip times (RTT) for variable packet sizes, and deduces capacity from the different RTTs measured. VPS uses the IP Time-To-Live parameter to measure individual hops. One major downside of VPS is that it does not work correctly when the path of the probe includes multiple network links, or multiple switches. One result of this is that VPS can underestimate path capacity. The way around this is to break down the network and apply VPS probing to the individual links that make up a path. This increases considerably the pre-knowledge needed to apply the method effectively to a network and the complexity of the method applied in an individual case. However, even this breaks down if switches or other layer-2 or layer-1 devices are included in the network. A domestic network typically includes such devices.
PGM probing uses 2 back-to-back probe packets of the same size. Sending two packets back-to-back means there is no delay in sending between the two packets and the skilled person knows what this means and how to achieve this. As these packets travel across various network links to their destination they will suffer various delays.
Serialization delay in a network is the delay caused by the bandwidth of the medium on which packets are sent. It is the time that is needed to transmit the packet. For a packet of size L (bits) at a link of transmission rate C (bits/s), the serialization delay is equal to L/C. For example, to send a packet of 10,000 bits on a link with a transmission rate of Ser. No. 10/000,000 bits/second, it will take 0.001 second or 1 millisecond to transmit the packet. Serialization delay is dependent on the packet size and is the time it takes to actually transmit a packet.
Queuing delay is the delay suffered by a probing packet because of cross traffic. If multiple data streams are sent across the same network link, they are normally queued and buffered and then transmitted one packet at the time on the network link. This can mean that a probing packet is buffered for a certain amount of time, awaiting its turn to be transmitted. This delay is called queuing delay. Note that such queuing delay can occur in any device on the path between sender and receiver, including the sender itself. Since this delay is dependent on other data packets, it is independent on the probing packet size.
Propagation delay is the time it takes for a packet to physically traverse a network link and is dependent on the medium used for transmission but independent of the packet size. For example, on a 50 meter ethernet cable (CAT-cable), the propagation delay is 50 m/177,000,000 m/s=0.28 μs. Putting a 1500 byte packet (maximum normal ethernet packet size) on a 1 Gbit/s network link causes a serialization delay of 1500*8 bits/1,000,000,000 bits/s=12 μs. The propagation delay in this example is only 2.3% of the serialization delay. Thus, unless packets travel for very long distances or on very high network speeds, the propagation delay is negligible in most cases when performing network measurements.
There is also a processing delay to be taken into account. To enable measurements the probe sender and the probe receiver put a timestamp on a probe packet for ‘packet sent’ and for ‘packet received’. However, the part of the device putting the timestamp on the packet is usually somewhere in the software of the device and is not part of the network interface card itself. Thus, when sending a packet, there is a small amount of time between the time of putting the timestamp on the packet and the actual transmission of the packet on the network. Similarly, there is a small amount of time between the actual receiving of a packet and the time of putting the timestamp on it and this small difference is called processing delay.
A final delay to be taken into account is probe reply delay, the delay caused by a receiver of a probe packet. It is the time taken to receive a probe and sent out a reply.
For determining a path's capacity with PGM, the queuing delay must be zero. Assuming the cross traffic having stochastic properties, a long enough series of probing measurements will yield at least one measurement where the queuing delay is zero. The measurement is identified by taking the minimum delay of probe packets of a number of measurements. If not negligible, the propagation delays of the PGM probes will be equal since both probe packets travel the same links. Furthermore, since the packets are of equal size, processing delays, probe reply delays and serialization delays will also be the same for both packets.
What is different, however, is the serialization delay for each network link. Network links with higher speeds have smaller serialization delays, network links with lower speeds have higher serialization delays. As both probe packets travel across different links, they are dispersed based on the serialization delays. The initial dispersion is caused by the first link, as the probe sender transmits the packets on the network. Each time the probe packets encounter a network link that is faster than at least one previously travelled slower link, the dispersion remains the same. But, each time the probe packets encounter a network link that is slower than any previously travelled link, the dispersion will increase due to the longer serialization delay.
Since the size of the dispersion between the two probe packets at the receiver is determined by the slowest network links, this means that PGM can be used to measure the bottleneck link on the probe path and in fact PGM can only measure the bottleneck link.
Capacity on this bottleneck link can be determined by using the following formula:
  C  =            L                        Ta                      PK            ⁢                                                  ⁢            2                          -                  Ta                      PK            ⁢                                                  ⁢            1                                =          L      D      where dispersion (D) is determined by subtracting the arrival time of the first packet (TaPK1) from the arrival time of the second packet (TaPK2). Capacity is then determined by dividing the size of the probe packets (L) by the dispersion.
The most advanced variety of PGM is described, for example, in Delphinanto, A. et al, “End-to-end available bandwidth probing in heterogeneous IP home networks”, Consumer Communications and Networking Conference (CCNC), 2011 IEEE, pp. 431-435, 9-12 Jan. 2011. This paper shows that PGM can also be used to determine bottleneck link speeds in heterogeneous networks consisting of links differing in speeds and medium, for example wired links and wireless links etc. The paper also shows that PGM can be performed with a separate source and receiver, but can also be performed using round-trip probes, for instance by probing with ping packets. The packets are of the same size in the forward and reverse direction.
Using PGM in a round-trip fashion does have a number of implications to keep in mind. Often, for round-trip measurements the popular Ping, i.e. ICMP request and reply, is used. An ICMP request and its reply are of similar size. When the network is symmetrical, i.e. the bandwidths on the links on the forward path are equal to the bandwidths on the links on the reverse path, using ICMP requests has no influence on the outcome, in other words the resulting bottleneck capacity is the same as if it were measured in a one-way PGM measurement. But, in case of asymmetric links, i.e. forward and reverse bandwidth being different, this does have an influence. In case of asymmetric links, the bottleneck link is in either one or the other direction. Actually, using ICMP requests in this way does not show if the network is symmetric or not, it only gives you the capacity of the bottleneck link.
The other much used probe packet, is an UDP packet to a so-called unused UDP port. Such an UDP packet will cause an ICMP “destination port unreachable” reply. Normally, the size of the UDP packet is chosen as large as possible, as this maximizes the size of the serialization delay which will lead to maximum achievable accuracy. The ICMP reply is a small-sized packet. Any serialization delay for the ICMP reply will be much smaller than the serialization delay of the probe packet on the bottleneck in the forward direction. Only on extremely asymmetric networks might this cause a problem if the serialization delay of the ICMP replies is larger than the serialization delays of the probe packets on the bottleneck link. As a result, probing with UDP generally yields the bottleneck link capacity in the forward direction only, irrespective of whether the measurement is performed using a one-way or round-trip.
Thus the skilled person knows that PGM determines bottleneck link capacity on a path because the probe packets are dispersed by the bottleneck link, but will not allow measurement of the capacities of other, non-bottleneck, links in the probing path. Modern probing methods attempt to derive as much information as possible about the network being probed, however, there are always gaps in the extracted information.
U.S. Pat. No. 6,795,401 B1 describes a bandwidth measuring method for a packet switching network in which a bandwidth of a packet switching network includes a plurality of nodes for packet switching connected mutually is measured, the method includes a procedure in which a plurality of test packets which at least include two test packets having different packet length are fed to the packet switching network so that in the two test packets, the test packet having a long packet length and the test packet having a short packet length are successive in this order, and a procedure in which a receiver receiving each test packet determines an immediately former bandwidth based on the difference in the reception completion timing thereof. This method has some disadvantages: for determining the packet sizes, the link speeds are required to be known. Furthermore, in case of multiple bottleneck links the method does not always work correctly.
It is a problem to find out as much as possible about the network being probed.